Multilog and data or-parallelism
Identifieur interne : 00BF46 ( Main/Exploration ); précédent : 00BF45; suivant : 00BF47Multilog and data or-parallelism
Auteurs : Donald A. Smith [Nouvelle-Zélande]Source :
- The Journal of Logic Programming [ 0743-1066 ] ; 1996.
English descriptors
- Teeft :
- Active environments, Average number, Backtracking, Backtracks, Benchmark, Benchmark results, Binding environments, Binding vector, Binding vectors, Choice point, Choice points, Choice stack, Combinatorial, Conf, Constraint, Constraint component, Constraint logic programming, Constructive negation, Control backtracks, Control operations, Control systems, Copying, Copying environments, Costa, Data structures, Different environments, Disj, Disjunct, Disjunction, Disjunctive, Disjunctive goal, Disjuncts, Dynamic reversion, Engine variables, Engine work, Environment trees, Execution model, Execution time, Finite domain restriction, Formal model, Goal component, Ksr1, Load balancing, Logic programming, Many environments, Maspar, Metric, Mimd, Mimd multilog, More solutions, Multi, Multiderivation, Multiheap, Multiheap variables, Multilog, Multilog program, Multiple binding environments, Multiple environments, Multiple solutions, Multiple substitutions, Multiresolution, Multiresolution steps, Multiunification, Multivariable, Multivariables, Next section, Nondeterministic, Normal multiresolution steps, Operational semantics, Optimization, Parallel implementation, Proc, Processor, Processor utilization, Programming, Prolog, Prolog engine, Prolog program, Query, Reversion, Reversion threshold, Same shape, Save_as_answer, Semantics, Sequential, Simd, Simd computers, Simd multilog, Simd processors, Single thread, Slowdown, Space usage, Speedup, Standard prolog, Subsequent goals, Subset, Substitution, Symp, Synchronization, Unification, Unification workers, Uniprocessor, Uniprocessor multilog, Variable vectors, Waltz, Worker environments.
Abstract
Abstract: This paper describes the design, implementation, performance, and analysis of MultiLog—a logic programming system whose distinguishing feature is the presence of multiple, concurrent binding environments (multiple substitutions) with a single thread of control. In MultiLog, for certain goals, some subset of the solutions is collected and installed as the active set of substitutions. Subsequent goals execute with unification performed concurrently on the multiple substitutions, using a single thread of control. In this way, multiple binding environments partially replace backtracking as the operational embodiment of disjunction. The slogan “one control, multiple environments” summarizes the “data or-parallelism” of MultiLog. In this paper, we present an operational semantics (multi-SLD resolution) for MultiLog; discuss MultiLog's design and implementation; display benchmark results for prototype uniprocessor, MIMD, and SIMD implementations; present performance models that explain observed speedups; and consider various extensions and generalizations. Our aim is to evaluate the viability of data or-parallelism as an alternative both to backtracking and to control or-parallel search.
Url:
DOI: 10.1016/S0743-1066(96)00067-2
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003C04
- to stream Istex, to step Curation: 003B60
- to stream Istex, to step Checkpoint: 002847
- to stream Main, to step Merge: 00C767
- to stream Main, to step Curation: 00BF46
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Multilog and data or-parallelism</title><author><name sortKey="Smith, Donald A" sort="Smith, Donald A" uniqKey="Smith D" first="Donald A." last="Smith">Donald A. Smith</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:FA7DD8883595A8604C85F2833B8451EEDB6A82AB</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1016/S0743-1066(96)00067-2</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-CXCBND3B-S/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003C04</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003C04</idno><idno type="wicri:Area/Istex/Curation">003B60</idno><idno type="wicri:Area/Istex/Checkpoint">002847</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002847</idno><idno type="wicri:doubleKey">0743-1066:1996:Smith D:multilog:and:data</idno><idno type="wicri:Area/Main/Merge">00C767</idno><idno type="wicri:Area/Main/Curation">00BF46</idno><idno type="wicri:Area/Main/Exploration">00BF46</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Multilog and data or-parallelism</title><author><name sortKey="Smith, Donald A" sort="Smith, Donald A" uniqKey="Smith D" first="Donald A." last="Smith">Donald A. Smith</name><affiliation wicri:level="1"><country xml:lang="fr">Nouvelle-Zélande</country><wicri:regionArea>Department of Computer Science, University of Waikato, Hamilton</wicri:regionArea><wicri:noRegion>Hamilton</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Nouvelle-Zélande</country></affiliation></author></analytic><monogr></monogr><series><title level="j">The Journal of Logic Programming</title><title level="j" type="abbrev">JLP</title><idno type="ISSN">0743-1066</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1996">1996</date><biblScope unit="volume">29</biblScope><biblScope unit="issue">1–3</biblScope><biblScope unit="page" from="195">195</biblScope><biblScope unit="page" to="244">244</biblScope></imprint><idno type="ISSN">0743-1066</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0743-1066</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Active environments</term><term>Average number</term><term>Backtracking</term><term>Backtracks</term><term>Benchmark</term><term>Benchmark results</term><term>Binding environments</term><term>Binding vector</term><term>Binding vectors</term><term>Choice point</term><term>Choice points</term><term>Choice stack</term><term>Combinatorial</term><term>Conf</term><term>Constraint</term><term>Constraint component</term><term>Constraint logic programming</term><term>Constructive negation</term><term>Control backtracks</term><term>Control operations</term><term>Control systems</term><term>Copying</term><term>Copying environments</term><term>Costa</term><term>Data structures</term><term>Different environments</term><term>Disj</term><term>Disjunct</term><term>Disjunction</term><term>Disjunctive</term><term>Disjunctive goal</term><term>Disjuncts</term><term>Dynamic reversion</term><term>Engine variables</term><term>Engine work</term><term>Environment trees</term><term>Execution model</term><term>Execution time</term><term>Finite domain restriction</term><term>Formal model</term><term>Goal component</term><term>Ksr1</term><term>Load balancing</term><term>Logic programming</term><term>Many environments</term><term>Maspar</term><term>Metric</term><term>Mimd</term><term>Mimd multilog</term><term>More solutions</term><term>Multi</term><term>Multiderivation</term><term>Multiheap</term><term>Multiheap variables</term><term>Multilog</term><term>Multilog program</term><term>Multiple binding environments</term><term>Multiple environments</term><term>Multiple solutions</term><term>Multiple substitutions</term><term>Multiresolution</term><term>Multiresolution steps</term><term>Multiunification</term><term>Multivariable</term><term>Multivariables</term><term>Next section</term><term>Nondeterministic</term><term>Normal multiresolution steps</term><term>Operational semantics</term><term>Optimization</term><term>Parallel implementation</term><term>Proc</term><term>Processor</term><term>Processor utilization</term><term>Programming</term><term>Prolog</term><term>Prolog engine</term><term>Prolog program</term><term>Query</term><term>Reversion</term><term>Reversion threshold</term><term>Same shape</term><term>Save_as_answer</term><term>Semantics</term><term>Sequential</term><term>Simd</term><term>Simd computers</term><term>Simd multilog</term><term>Simd processors</term><term>Single thread</term><term>Slowdown</term><term>Space usage</term><term>Speedup</term><term>Standard prolog</term><term>Subsequent goals</term><term>Subset</term><term>Substitution</term><term>Symp</term><term>Synchronization</term><term>Unification</term><term>Unification workers</term><term>Uniprocessor</term><term>Uniprocessor multilog</term><term>Variable vectors</term><term>Waltz</term><term>Worker environments</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: This paper describes the design, implementation, performance, and analysis of MultiLog—a logic programming system whose distinguishing feature is the presence of multiple, concurrent binding environments (multiple substitutions) with a single thread of control. In MultiLog, for certain goals, some subset of the solutions is collected and installed as the active set of substitutions. Subsequent goals execute with unification performed concurrently on the multiple substitutions, using a single thread of control. In this way, multiple binding environments partially replace backtracking as the operational embodiment of disjunction. The slogan “one control, multiple environments” summarizes the “data or-parallelism” of MultiLog. In this paper, we present an operational semantics (multi-SLD resolution) for MultiLog; discuss MultiLog's design and implementation; display benchmark results for prototype uniprocessor, MIMD, and SIMD implementations; present performance models that explain observed speedups; and consider various extensions and generalizations. Our aim is to evaluate the viability of data or-parallelism as an alternative both to backtracking and to control or-parallel search.</div></front></TEI><affiliations><list><country><li>Nouvelle-Zélande</li></country></list><tree><country name="Nouvelle-Zélande"><noRegion><name sortKey="Smith, Donald A" sort="Smith, Donald A" uniqKey="Smith D" first="Donald A." last="Smith">Donald A. Smith</name></noRegion><name sortKey="Smith, Donald A" sort="Smith, Donald A" uniqKey="Smith D" first="Donald A." last="Smith">Donald A. Smith</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00BF46 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00BF46 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:FA7DD8883595A8604C85F2833B8451EEDB6A82AB
|texte= Multilog and data or-parallelism
}}
| This area was generated with Dilib version V0.6.33. |  |